Say that a d.c.e. degree d is isolated by a c.e. degree b, if bMathematics Subject Classification (2000): 03D25, 03D30, 03D35 RID=""ID="" Key words or phrases: Computably enumerable (...) set – d.c.e. degree – Isolation – High/low hierarchy RID=""ID="" Ishmukhametov's research is supported by RFBR grant 01-01-00733, and Wu's research is supported by the Marsden Fund of New Zealand. Wu would like to thank his supervisor, Prof. Rod Downey, for his many helpful suggestions and comments. (shrink)

We show the existence of a high d. c. e. degree d and a low2 c.e. degree a such that d is isolated by a.

Say that (a, d) is an isolation pair if a is a c.e. degree, d is a d.c.e. degree, a < d and a bounds all c.e. degrees below d. We prove that there are an isolation pair (a, d) and a c.e. degree c such that c is incomparable with a, d, and c cups d to o', caps a to o. Thus, {o, c, d, o'} is a diamond embedding, which was first proved by Downey in [9]. Furthermore, (...) combined with Harrington-Soare continuity of capping degrees, our result gives an alternative proof of N5 embedding. (shrink)

In this paper, we solve a long-standing open question, about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering [Formula: see text] has infinitely many successivities, then the spectrum of the successivity relation is closed upwards in the computably enumerable Turing degrees. To do this, we use a new method of constructing [Formula: see text]-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [9] and is of (...) independent interest. It would seem to promise many further applications. (shrink)

Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper, we study the c.e. predecessors of d.c.e. degrees, and prove that given a nonzero d.c.e. degree , there is a c.e. degree below and a high d.c.e. degree such that bounds all the c.e. degrees below . This result gives a unified approach to some seemingly unrelated results. In particular, it has the following two known theorems as corollaries: there is a low c.e. degree isolating (...) a high d.c.e. degree [S. Ishmukhametov, G. Wu, Isolation and the high/low hierarchy, Arch. Math. Logic 41 259–266]; there is a high d.c.e. degree bounding no minimal pairs [C.T. Chong, A. Li, Y. Yang, The existence of high nonbounding degrees in the difference hierarchy, Ann. Pure Appl. Logic 138 31–51]. (shrink)

Say that a d.c.e. degree d is nonisolated if for any c.e. degree a

Logic and Philosophy of Logic

Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic

Direct download (4 more)  

 

Export citation  

 

Bookmark   2 citations  

The notion of superhigh computably enumerable (c.e.) degrees was first introduced by (Mohrherr in Z Math Logik Grundlag Math 32: 5–12, 1986) where she proved the existence of incomplete superhigh c.e. degrees, and high, but not superhigh, c.e. degrees. Recent research shows that the notion of superhighness is closely related to algorithmic randomness and effective measure theory. Jockusch and Mohrherr proved in (Proc Amer Math Soc 94:123–128, 1985) that the diamond lattice can be embedded into the c.e. tt-degrees preserving 0 (...) and 1 and that the two atoms can be low. In this paper, we prove that the two atoms in such embeddings can also be superhigh. (shrink)

We prove that for any computably enumerable degree c, if it is cappable in the computably enumerable degrees, then there is a d.c.e. degree d such that c d = 0′ and c ∩ d = 0. Consequently, a computably enumerable degree is cappable if and only if it can be complemented by a nonzero d.c.e. degree. This gives a new characterization of the cappable degrees.

In [Countable thin [Formula: see text] classes, Ann. Pure Appl. Logic 59 79–139], Cenzer, Downey, Jockusch and Shore proved the density of degrees containing members of countable thin [Formula: see text] classes. In the same paper, Cenzer et al. also proved the existence of degrees containing no members of thin [Formula: see text] classes. We will prove in this paper that the c.e. degrees containing no members of thin [Formula: see text] classes are dense in the c.e. degrees. We will (...) also prove that the c.e. degrees containing members of thin [Formula: see text] classes are dense in the c.e. degrees, improving the result of Cenzer et al. mentioned above. Thus, we obtain a new natural subclass of c.e. degrees which are both dense and co-dense in the c.e. degrees, while the other such class is the class of branching c.e. degrees 113–130] for nonbranching degrees and [T. A. Slaman, The density of infima in the recursively enumerable degrees, Ann. Pure Appl. Logic 52 155–179] for branching degrees). (shrink)

A real α is called a c. e. real if it is the halting probability of a prefix free Turing machine. Equivalently, α is c. e. if it is left computable in the sense that L = {q ∈ ℚ : q ≤ α} is a computably enumerable set. The natural field formed by the c. e. reals turns out to be the field formed by the collection of the d. c. e. reals, which are of the form α—β, where (...) α and β are c. e. reals. While c. e. reals can only be found in the c. e. degrees, Zheng has proven that there are Δ02 degrees that are not even n-c. e. for any n and yet contain d. c. e. reals, where a degree is n-c. e. if it contains an n-c. e. set. In this paper we will prove that every ω-c. e. degree contains a d. c. e. real, but there are ω + 1-c. e. degrees and, hence Δ02 degrees, containing no d. c. e. real. (shrink)

Given a d.c.e. degree d, consider the d.c.e. sets in d and the corresponding degrees of their Lachlan sets. Ishmukhametov provided a systematic investigation of such degrees, and proved that for a given d.c.e. degree d > 0, the class of its c.e. predecessors in which d is c.e., denoted as R[d], can consist of either just one element, or an interval of c.e. degrees. After this, Ishmukhametov asked whether there exists a d.c.e. degree d for which the class R[d] (...) has no minimal element. We give a positive answer to this question. (shrink)

We characterize the linear order types $\tau $ with the property that given any countable linear order $\mathcal {L}$, $\tau \cdot \mathcal {L}$ is a computable linear order iff $\mathcal {L}$ is a computable linear order, as exactly the finite nonempty order types.

We show that there is a cuppable c.e. degree, all of whose cupping partners are high. In particular, not all cuppable degrees are${\operatorname {\mathrm {low}}}_3$-cuppable, or indeed${\operatorname {\mathrm {low}}}_n$cuppable for anyn, refuting a conjecture by Li. On the other hand, we show that one cannot improve highness to superhighness. We also show that the${\operatorname {\mathrm {low}}}_2$-cuppable degrees coincide with the array computable-cuppable degrees, giving a full understanding of the latter class.

In this paper, we study the bi-isolation phenomena in the d.c.e. degrees and prove that there are c.e. degrees c₁ < c₂ and a d.c.e. degree d ∈ (c₁, c₂) such that (c₁, d) and (d, c₂) contain no c.e. degrees. Thus, the c.e. degrees between c₁ and c₂ are all incomparable with d. We also show that there are d.c.e. degrees d₁ < d₂ such that (d₁, d₂) contains a unique c.e. degree.

In [9]. Yates proved the existence of a Turing degree a such that 0. 0′ are the only c.e. degrees comparable with it. By Slaman and Steel [7], every degree below 0′ has a 1-generic complement, and as a consequence. Yates degrees can be 1-generic, and hence can be low. In this paper, we prove that Yates degrees occur in every jump class.

Say that an incomplete d.r.e. degree has almost universal cupping property, if it cups all the r.e. degrees not below it to 0′. In this paper, we construct such a degree d, with all the r.e. degrees not cupping d to 0′ bounded by some r.e. degree strictly below d. The construction itself is an interesting 0″′ argument and this new structural property can be used to study final segments of various degree structures in the Ershov hierarchy.

Lachlan observed that the infimum of two r.e. degrees considered in the r.e. degrees coincides with the one considered in the ${\Delta_2^0}$ degrees. It is not true anymore for the d.r.e. degrees. Kaddah proved in (Ann Pure Appl Log 62(3):207–263, 1993) that there are d.r.e. degrees a, b, c and a 3-r.e. degree x such that a is the infimum of b, c in the d.r.e. degrees, but not in the 3-r.e. degrees, as a < x < b, c. In (...) this paper, we extend Kaddah’s result by showing that such a structural difference occurs densely in the r.e. degrees. Our result immediately implies that the isolated 3-r.e. degrees are dense in the r.e. degrees, which was first proved by LaForte. (shrink)

Cholak, Groszek and Slaman proved in J Symb Log 66:881–901, 2001 that there is a nonzero computably enumerable (c.e.) degree cupping every low c.e. degree to a low c.e. degree. In the same paper, they pointed out that every nonzero c.e. degree can cup a low2 c.e. degree to a nonlow2 degree. In Jockusch et al. (Trans Am Math Soc 356:2557–2568, 2004) improved the latter result by showing that every nonzero c.e. degree c is cuppable to a high c.e. degree (...) by a low2 c.e. degree b. It is natural to ask in which subclass of low2 c.e. degrees can b in Jockusch et al. (Trans Am Math Soc 356:2557–2568, 2004) be located. Wu proved in Math Log Quart 50:189–201, 2004 that b can be cappable. We prove in this paper that b in Jockusch, Li and Yang’s result can be noncuppable, improving both Jockusch, Li and Yang, and Wu’s results. (shrink)

In this paper, we improve a result of Seetapun and prove that above any nonzero, incomplete recursively enumerable degree a, there is a high2 r.e. degree c>ac>a witnessing that a is locally noncappable . Theorem 1.1 provides a scheme of obtaining high2 nonboundings , as all known high2 nonboundings, such as high2 degrees bounding no minimal pairs, high2 plus-cuppings, etc.

Say a set Gω is 1-generic if for any eω, there is a string σG such that {e}σ↓ or τσ↑). It is known that can be split into two 1-generic degrees. In this paper, we generalize this and prove that any nonzero computably enumerable degree can be split into two 1-generic degrees. As a corollary, no two computably enumerable degrees bound the same class of 1-generic degrees.

Cooper proved in [S.B. Cooper, Strong minimal covers for recursively enumerable degrees, Math. Logic Quart. 42 191–196] the existence of a c.e. degree with a strong minimal cover . So is the greastest c.e. degree below . Cooper and Yi pointed out in [S.B. Cooper, X. Yi, Isolated d.r.e. degrees, University of Leeds, Dept. of Pure Math., 1995. Preprint] that this strongly minimal cover cannot be d.c.e., and meanwhile, they proposed the notion of isolated degrees: a d.c.e. degree is isolated (...) by a c.e. degree if is the greatest c.e. degree below , and we also say that isolates . In [G. Wu, Bi-isolation in the d.c.e. degrees, J. Symbolic Logic 69 409–420], Wu extended Cooper–Yi’s notion and proved that there are intervals of d.c.e. degrees containing exactly one c.e. degree . Following Cooper and Yi’s notion, is called a bi-isolating degree. The bi-isolating degrees are dense in the high c.e. degrees. Arslanov asked whether the bi-isolating degrees occur in every jump class. In this paper, we prove that there are low bi-isolating degrees, providing a partial solution to Arslanov’s question. (shrink)

We give a characterization of strongly compact cardinals in terms of Q κ λ. We also prove that weakly normal Q-measures on Q κ λ are ⊂κ-normal.

We give a characterization of strongly compact cardinals in terms of Qκλ. We also prove that weakly normal Q-measures on Qκλ are ⊂κ-normal.

Say that a nonzero c. e. degree b is a quasi-complement of a c. e. degree a if a ∩ b = 0 and a ∪ b is high. It is well-known that each cappable degree has a high quasi-complement. However, by the existence of the almost deep degrees, there are nonzero cappable degrees having no low quasi-complements. In this paper, we prove that any nonzero cappable degree has a low2 quasi-complement.

Say that α is an n-strongly c. e. real if α is a sum of n many strongly c. e. reals, and that α is regular if α is n-strongly c. e. for some n. Let Sn be the set of all n-strongly c. e. reals, Reg be the set of regular reals and CE be the set of c. e. reals. Then we have: S1 ⊂ S2 ⊂ · · · ⊂ Sn ⊂ · · · ⊂ ⊂ Reg (...) ⊂ CE. This gives a hierarchy of the c. e. reals. We also study the regularity of the d. c. e. reals. (shrink)